package leetcode.code189.RotateArray;

import java.util.HashSet;
import java.util.Set;

/**
 * 一次一个不行啊
 *
 * @author Max
 * @date 2021年8月13日
 * @description
 */
public class GuessRing implements IRotateArray {

	@Override
	public void rotate(int[] nums, int k) {
		int len = nums.length;
		int gcd = gcd(len, k);
		int groupSize = len / gcd;
		for (int i = 0; i < gcd; i++) {
			int start = nums[i];
			int step = i;
			for (int j = 0; j < groupSize; j++) {
				step = (step + k) % len;
				int temp = nums[step];
				nums[step] = start;
				start = temp;
			}
		}
	}

	public int gcd(int m, int n) {
		return n == 0 ? m : gcd(n, m % n);
	}

	/**
	 * 从0开始，步长为step的下标特点
	 *
	 * @param len
	 * @param step
	 */
	public void printIndex(int len, int step, boolean print) {
		Set<Integer> set = new HashSet<>();
		int start = -1;
		int ring = 0;
		while (set.size() != len) {
			start++;
			if (set.contains(start)) {
//				System.out.println(">" + start + "<");// 被处理过
				break;
			}
			System.out.println("start : " + start);
			int min = Integer.MAX_VALUE;
			while (true) {
				start = start + step;
				if (start >= len) {
					start = start % len;
				}
				if (set.contains(start)) {
					ring++;
//					System.out.println("??"+start+"??");
					break;
				}
				if (print)
					System.out.print(start + ",");
				min = min > start ? start : min;
				set.add(start);
			}
			System.out.println("min : " + min);
//			System.out.println("");
		}
		System.out.println("数量：" + len + " 步长：" + step + " 环:" + ring);

	}

	public void myPrint1(int k) {
//		输入: nums = [1,2,3,4,5,6,7], k = 3
//		输出: [5,6,7,1,2,3,4]
		int[] nums = { 1, 2, 3, 4, 5, 6, 7 };
//		int k = 1;
		this.myDebug(nums, k);
	}

	public void myPrint2(int k) {
//		输入：nums = [-1,-100,3,99], k = 2
//		输出：[3,99,-1,-100]
		int[] nums = { -1, -100, 3, 99 };
//		int k = 1;
		this.myDebug(nums, k);
	}

	private void myDebug(int[] nums, int k) {
//		for (int num : nums) {
//			System.out.print(num + ",");
//		}
//		System.out.println(" ");

		IRotateArray ira = new GuessRing();
		ira.rotate(nums, k);
		System.out.println(k + ">>");
		for (int num : nums) {
			System.out.print(num + ",");
		}
		System.out.println(" ");

	}

	public static void main(String[] args) {
		GuessRing so = new GuessRing();
//		so.myPrint1();
//		so.myPrint2();
//		so.myPrint(10);

//		int[] nums = new int[20000];
//		for (int i = 0; i < 20000; i++) {
//			nums[i] = i;
//		}
//		so.rotate(nums, 11939);
//		System.out.println(20000 + ">>");
//		int line = 0;
//		for (int num : nums) {
//			System.out.print(num + ",");
//			line++;
//			if (line == 99) {
//				System.out.print(num + ",");
//				line = 0;
//			}
//		}
//		System.out.println(" ");
		// 偶数 偶数步有环 ，半的时候环最多
//		for (int i = 999; i < 1000; i++)
//			for (int j = 1; j < i; j++) {
//				so.printIndex(i, j, false);
//			}

		// 最大公约数
//		int result = so.gcd(999, 962);
//		System.out.println(result);

//		so.printIndex(999, 962, false);
//		so.printIndex(10, 3, true);

//		for (int i = 0; i < 12; i++) {
//			System.out.println(i);
//			so.printIndex(9, i);
//			System.out.println(" ");
//		}

		so.myPrint2(2);
	}

	private void myPrint(int k) {
		for (int i = 0; i < k; i++) {
//			this.myPrint1(i);
			this.myPrint2(i);
		}

	}

}
